/**
 *	The NeuroCoSA Toolkit
 *	Copyright (C) 2003-6 Stuart Meikle.
 *
 *	This is free software; you can redistribute it and/or
 *	modify it under the terms of the GNU Lesser General Public
 *	License as published by the Free Software Foundation; either
 *	version 2.1 of the License, or (at your option) any later version.
 *
 *	This library is distributed in the hope that it will be useful,
 *	but WITHOUT ANY WARRANTY; without even the implied warranty of
 *	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *	Lesser General Public License for more details.
 *
 * @author	Stuart Meikle
 * @version	2006-halloween(mk2)
 * @license	LGPL
 */
package org.stumeikle.NeuroCoSA.AutoCluster;

/**
 * Hash_table .h in java form.
 * A memory , similar to STLTMemory but based on autocluster
 *
 * stumeikle 20060408
 *
 */
 
import java.util.*;


public	class	AutoClusterMemoryControl
{
    //public static finals go in here
    //but would be better if these were user definable
    private	int		iNumBins;
    private	int		iMaxNumBins;
    private	long		iTotalNumEntries;
    private	LinkedList<AutoClusterMemory>	iBins;
    private	LinkedList<AutoClusterMemory>	iConsolBins; //consolidated bins
    private	double		iSizeOfNewBins;
    private	AutoClusterMemory	iScrapBin; //pointer to
    private	Random		iRand;
    private	long		iCurrentTime;
    private	long		iNextId;
    private	long		iMaxNumInScrapBin;
    private	long		iNoiseLifeTime;
    private	AutoClusterNeuroCoSAIF	iOutsideWorld;
    
    public AutoClusterMemoryControl( int max_bins, double size_of_new_bins, 
    				     long max_num_in_scrap_bin, long lifetime_of_noise,
    				     AutoClusterNeuroCoSAIF nif  )
    { 
        iNumBins = 0;
	iMaxNumBins = max_bins; //USER DEFINABLE
	iTotalNumEntries = 0;
	iScrapBin = null;
	iBins = new LinkedList<AutoClusterMemory>();
	iConsolBins = new LinkedList<AutoClusterMemory>();
	iRand = new Random();
	iSizeOfNewBins = size_of_new_bins;
	iCurrentTime = 1;
	iNextId=1;
	iMaxNumInScrapBin = max_num_in_scrap_bin;
	iNoiseLifeTime = lifetime_of_noise;
	iOutsideWorld = nif;
    }

    //hash_bin	*getScrapBin(){ return scrap_bin; }
    public AutoClusterMemory	getScrapBin()
    { return iScrapBin; }
    
    //	list<hash_bin*>	*getBins(void)
    public LinkedList		getBins()
    { return iBins; }
    
    //list<hash_bin*>	*getConsolidatedBins(void)
    public LinkedList		getConsolidatedBins()
    { return iConsolBins; }

    public int			getNumBins()
    { return iNumBins;}
    
    public int			getMaxNumBins()
    { return iMaxNumBins;}
    
    public void			setMaxNumBins(int n)
    { iMaxNumBins = n; }		

    public void			removeBin( AutoClusterMemory b )
    {
        iBins.remove(b);
	    
	//delete the actual data
	b = null;
	iNumBins--;
    }
    
    public void			addValue( NMeasurable t, long curr_time )
    {
        //this is the master addvalue function which not only adds values 
 	//to the hash table, it also periodically tidies everything up, and
	//so on
	//tabletime++; //FIX ME
    
        //(0) set the size which should be used for new bins
        //(arbitrary - i guess distance measurements should be normalised or
        // something ideally)
        //iSizeOfNewBins = SIZE_OF_NEW_BINS; FIX ME
    
        //(1) first thing -> store the new value in the histogram
        //	  either in an existing bin, or inside a new one if nec.
        iCurrentTime = curr_time;
        storeValue(t,false,iNumBins);
    
        //(2) after some time ...
        //check that all the bins are ok in their contents.
        //(bins with 2* or 0.5* the 'mean' should cause us to stop and 
        //reassess the bin allocations, resizing and splitting as necessary)#
        // -- we don't really need to do this every time -- 
        lookForMelds();
        checkIfMoreBinsNeeded();
        checkForBinSplits();
        checkForNoiseBins();
        checkForUnchangingBins();

        //(3) somewhere we also need to update the centroid positions 
    }

    public void 		testValue( NMeasurable t, long test_time )
    {
	//compare the given value to the centroids of the available bins
	//store the distanes in the bins themselves. Don't update anything however
	//NeuroCoSA will use this to store drive values in the network
	//OPTIMISE: we could somehow combine this with storevalue to improve our
	//efficiency	       

	//store the test time -> this gives the owners of the memories a 
	//mechanism to check whether or not the learn and drive signals have been
	//updated this BrainTime. If not then they shouldn't act on them
        ListIterator	i = iBins.listIterator(0);
	if (t==null)	return;
    
    	for(;i.hasNext();)
    	{
    	    AutoClusterMemory	mem = (AutoClusterMemory)i.next(); 
	
	    //mem.storeTestDistance( AutoClusterMemory.UNDEFINED_DISTANCE );
	    if (mem.getIgnore()==true)
	    	continue;
	    	
	    //calculate the distance between the has bin centroid and 
	    //the entry
	    double		d;
	    NMeasurable		nt = mem.getCentroid();
	    d = t.distanceTo(nt); 

	    //store this distance in each acm so that it can be later 
	    //retrieved by neurocosa ...
	    mem.storeTestDistance(d, test_time);
        } 
        
        i = iConsolBins.listIterator(0);
        for(;i.hasNext();)
        {  
            AutoClusterMemory	mem= (AutoClusterMemory) i.next();
        
	    //mem.storeTestDistance( AutoClusterMemory.UNDEFINED_DISTANCE, test_time );
            if (mem.getIgnore())	continue;
    
	    //calculate the distance between the has bin centroid and 
	    //the entry
	    double		d;
	    NMeasurable		nt = mem.getCentroid();
	
	    d = t.distanceTo( nt );//yes, we could overload the
				   //operator   
	    mem.storeTestDistance( d, test_time );
        }     
    }
    
    public void			storeValue( NMeasurable t, boolean afterbreak ,int n)
    {
        //add the value to the hash table
        //ONLY store it. do nothing else with the hash table.
        //use the next_size var to chose an appropriate size for any
        //new bins created

        //ALGO:
        //check all bins and find out which bin the value lies within
        //It is entirely possible for the value to exist within more
        //than one bin. we will assume that the closest centroid wins.  
        //(this might have problems if there are a lot of bins within
        //a single larger bin)
    
        //if its outside of all bins, then we'll have to do something
        //special with it. (like creating a new bin probably)
        // 	alternatively we could stick it somewhere outside and 
        //wait until there are a significant number out there before 
        //we consider adding a new node. 
        boolean		inside = false;
        double		min_distance;
        double		min_outside_distance;
	AutoClusterMemory closest = null;
	AutoClusterMemory closest_out = null;
	
        //if this is the first entry into a given bin, then do something
        //special... (set the centroid to that value etc)
	min_distance=min_outside_distance=-1.0;
    	ListIterator	i = iBins.listIterator(0);
    
    	for(;i.hasNext();)
    	{
    	    AutoClusterMemory	mem = (AutoClusterMemory)i.next(); 
	
  	    mem.storeDistance( AutoClusterMemory.UNDEFINED_DISTANCE, iCurrentTime );
	    if (mem.getIgnore()==true)
	    	continue;
	    	
	    //calculate the distance between the has bin centroid and 
	    //the entry
	    double		d;
	    NMeasurable		nt = mem.getCentroid();
	    d = t.distanceTo(nt); 

	    //store this distance in each acm so that it can be later 
	    //retrieved by neurocosa ...
// 	    mem.storeDistance(d, iCurrentTime);
	    //last line removed by stumeikle 20060510 . multiple learning neurons breaks grasping

 	    if (d<mem.getSize())	//radius essentially
	    {
	        inside = true;
 	        if (d<min_distance || min_distance==-1.0)
	        {
    		    min_distance = d;
		    closest =mem;
	        }
	    }else if (d<min_outside_distance || min_outside_distance==-1.0)
	    {
	        min_outside_distance=d;
	        closest_out =mem;
	    }
        } 
        
        i = iConsolBins.listIterator(0);
        for(;i.hasNext();)
        {  
            AutoClusterMemory	mem= (AutoClusterMemory) i.next();
        
  	    mem.storeDistance( AutoClusterMemory.UNDEFINED_DISTANCE, iCurrentTime );
            if (mem.getIgnore())	continue;
    
	    //calculate the distance between the has bin centroid and 
	    //the entry
	    double		d;
	    NMeasurable		nt = mem.getCentroid();
	
	    d = t.distanceTo( nt );//yes, we could overload the
				   //operator   
// 	    mem.storeDistance( d, iCurrentTime ); removed 20060510
			
	    if (d<mem.getSize())	//radius essentially
	    {
	        inside = true;
	        if (d<min_distance || min_distance==-1.0)
	        {
    		    min_distance = d;
		    closest = mem;
	        }
	    }else if (d<min_outside_distance || min_outside_distance==-1.0)
	    {
	        min_outside_distance=d;
	        closest_out =mem;
	    }
        } 

	if (closest !=null)
	    closest.storeDistance( min_distance, iCurrentTime );
    
   
        if (inside==true)
        {
 	    //inside a bin, so simply add the entry to the bin
	    addCT2Bin( t, closest );
        }
        else
        {
	    //do something special if it's outside the bin
	    //(either create a new bin, or store it in the nearest one anyway)
	    if (n < iMaxNumBins)
	    {
	        //@@@ futurefeature -> don't create an arbitrarily large bin!
	        //@@@ consider the distance to the nearest bin
	    
	        //basially if this is a new point then we can find a resonable 
	        //distance / size value . if its occuring from a splitting of
	        //two bins, then we can't.
	    	if (min_outside_distance==-1)
	    	    min_outside_distance=iSizeOfNewBins;
	        if (!afterbreak)	    
		    createNewBin( t, min_outside_distance );
	        else
		    createNewBin( t, iSizeOfNewBins );
	    }
	    else
	    {
	        //point lies outside a bin, but we can't create any more bins
	        //answer = increase the size of the nearest bin until it is within it!
	        //@ we should probably recalc the centroid and iterate and everything
	        //but i won't do that for now

	        //add to the scrap bin for now
	        if (iScrapBin == null)
	        {
		    //dont need to inform the outside world about this (?)
		    //because its scrap and dosen't need an external representation
	            AutoClusterMemory	mem= new AutoClusterMemory( t, Double.MAX_VALUE,
            						iCurrentTime, iNextId++ );
		    iScrapBin = mem;	        	
	    	
		    addCT2Bin( t, mem );
	   	}else
	        {
	    	    addCT2Bin( t, iScrapBin );
	        }
	    }
	}
    }
    
    public	void	createNewBin( NMeasurable t , double s )
    {
        // (we've already checked the number of bins)
        // create a new bin. set the centroid value to the position of t
        // add t to its list of entries, set the size according to the external size
        // parameter. 
    
        //(1) we need to duplicate the data for use as the centroid, or it'll be 
        //deleted twice. (i'll try and be clever and use the copy constructor)
        
        if (iOutsideWorld.requestNewACM() == false)	return;
	if (t==null)					return;
        
        if (s>iSizeOfNewBins)  	s=iSizeOfNewBins;
    
        NMeasurable 		tb = t.createCopy();
        AutoClusterMemory	hb = new AutoClusterMemory(tb, s, 
        						   iCurrentTime, iNextId++);
	hb.storeDistance( 0.0, iCurrentTime );
	addCT2Bin( t, hb );
	iNumBins++;
        
        iBins.add(hb);
        
        iOutsideWorld.setNewACM( hb );
    }

    public	void		lookForMelds()
    {
        // algo. 
        // take 2 random bins
        // if they do not significantly overlap in space then return
        // else.
        // create a 1d hough. fill in all the points to estabilsh a graph of 
        // num points along a line through the centre of both bins.
        // size of the hough does not probably matter
        // test for merge:
        // for each bin: is the max density at the bin bounary ? 
        // if yes ->
        // if the difference between max and min density is > some noise threshold
        // then merge the bins
        //in FUTURE use nearest neighbour bins and not just random ones
    
        //(1) find 2 bins and check for overlap
        double	n1 = iRand.nextDouble() * (double)iNumBins;
        double	n2 = iRand.nextDouble() * (double)iNumBins;
    
        if (iNumBins==0)		return;
        if ((int)n1==(int)n2)		return;
    
    	AutoClusterMemory		h1, h2;
	ListIterator			i;
	int				j;
    
	h1=h2=null;	j=0;
	i = iBins.listIterator(0);
        for(j=0;i.hasNext();j++)
        {
            AutoClusterMemory	hb = (AutoClusterMemory) i.next();
        
            if (j==(int)n1)	h1 = hb;
            if (j==(int)n2)	h2 = hb;
        }
        
        if ((h1.getSize() + h2.getSize()) > h1.getCentroid().distanceTo
            (h2.getCentroid() ) )
        {
	    checkForMeld( h1, h2 );
     	    checkForMeld( h2, h1 );
        }
    }
    
    public	void	checkForMeld( AutoClusterMemory hb1, AutoClusterMemory hb2 )
    {
        //(0) I want to change this now (20060324) so that we only 
        //	  feed in points from one of the bins, to allow bins to merge
        //	  with consolidated bins. We're just looking for a steady 
        //	  gradient from one bin to another. let's look for hb1 merging
        //	  with hb2. merge the two if there is a steady gradient from
        //	  points in hb1 to hb2
        //(0.5) if both bins are consolidated though there's no chance to merge
        if (hb1.isConsolidated()==true && hb2.isConsolidated()==true)
        { 	return;     }

        //(1) allocate a hough to space the distance between the two bins
        //	  Need to choose the number of bins to ensure a smooth distribution.
        //	  Could look for the max distance between nns and use that to set
        //	  the bin size. 
        //	  Or we could wait until there are at least x points in each bin
        int	arraysize=10;
        double	hough[];
        double	maxr[];
        int	i;
        int	c1max=0,c2min=arraysize-1;
        long	total=0;
    
        hough = new double[arraysize];
        maxr  = new double[arraysize];
    
        for(i=0;i<arraysize;++i)
        {
            hough[i]=0.0;
     	    maxr[i]=-1.0;
        }
    
        //(1.5) calcualte some needed vars;
        double		cmag,vmag;
        double		xscale;
        NMeasurable     hb1_cen, hb2_cen;
        NMeasurable	c_vec, v_vec;
        hb1_cen = hb1.getCentroid();
        hb2_cen = hb2.getCentroid();
        
        c_vec = hb2_cen.createCopy();
        c_vec.subtract( hb1_cen );
	cmag = c_vec.magnitude();
	
        if (cmag < 0.001)	return;
        xscale = arraysize / cmag;
    
        //(2) feed in all the points
        ListIterator			it;
	it = hb1.getEntryList().listIterator(0);
	for(;it.hasNext();)
	{
	    NMeasurable		c= (NMeasurable ) it.next();
            double		x,y;
	    int			ix;
        
	    //transform the position of c
            //add to the hough
	    v_vec = c.createCopy();
	    v_vec.subtract( hb1_cen );
	    
	    //reduce to 2 dimensions -> distance along line between centres
	    //(x) and distance perpendicular to this line (y)
	    x = v_vec.dotProduct( c_vec ) / cmag;
            vmag = v_vec.magnitude();
     	    y = Math.sqrt( vmag*vmag - x*x );
            x *= xscale;
            ix = (int)Math.floor(x);
            if (ix >=0 && ix<arraysize)
            {
                hough[ix]+=1.0;
                total++;
                if (ix>c1max)	c1max=ix;
                if ( y> maxr[ix] || maxr[ix]==-1.0)
                maxr[ix]=y;
            }
        }
        
        //can still feed these in if they're available. 
        it = hb2.getEntryList().listIterator(0);
	for(;it.hasNext();)
	{
	    NMeasurable		c= (NMeasurable) it.next();
            double		x,y;
	    int			ix;
        
	    //transform the position of c
            //add to the hough
	    v_vec = c.createCopy();
	    v_vec.subtract( hb1_cen );
	    
	    //reduce to 2 dimensions -> distance along line between centres
	    //(x) and distance perpendicular to this line (y)
	    x = v_vec.dotProduct( c_vec ) / cmag;
            vmag = v_vec.magnitude();
     	    y = Math.sqrt( vmag*vmag - x*x );
            x *= xscale;
            ix = (int)Math.floor(x);
            if (ix >=0 && ix<arraysize)
            {
                hough[ix]+=1.0;
                total++;
                if (ix<c2min)	c2min=ix;                
                if ( y> maxr[ix] || maxr[ix]==-1.0)
                maxr[ix]=y;
            }
        }

        //(2.5) if the total content of the bins is < 10 then discard -
        //not enough info / errors too high 
        if (total<10)	return;   

        //(2.7) process the data a little more -> estimate density at each
        //point
        for(i=0;i<arraysize;i++)
        {
            if (maxr[i]>0.0)	hough[i]/=maxr[i];
            else		hough[i]=0.0;
        }

        //(3) analyse. check if there's a smooth gradient.
        // [20060324 from 0 to c1max
        // if not, return.
        // if yes then take the stronger of hb1 and hb2 and merge
        // There's a problem at the bin edges strangely
        boolean	monotonic =true;

        for(i=1;i<=c1max;i++)
        {
    	    double	d = hough[i] - hough[i-1];
    	
            if (d>0) continue;
            monotonic=false;
    	    break;
        }

        if (monotonic==true)
        {
//        if (hough[0] > hough[size-1])
//        {
//            //merge. keep hb1 and remove hb2
//            mergeBins( hb1, hb2 );
//            cout << "Merge needed" << endl;
//       }else
            //merge. keep hb2 and remove hb1
            mergeBins( hb2, hb1 );
        }
    }
    
    public	void		checkIfMoreBinsNeeded()
    {
        //find the densest part of the scrap bin or chose a random point
        //add up the number of entries within new-bin-size distance
        //compare the number of entries to those within the neighbouring bins
        //create more bins if nec (that doesn't make sense really)
        //if more bins are not allowed then increase the size of new bins
        //or something
        if (iScrapBin==null)	return;
   	if (iNumBins==0)	return;
  
	long	randbin =(long)(iRand.nextDouble() *
    			 (double)iScrapBin.getEntryList().size());
	long	bincount = 0;
    	double	nn_dist = -1.0;
	AutoClusterMemory	nn;
    	NMeasurable		chosen = null;
	ListIterator		i;
    	
    	i = iScrapBin.getEntryList().listIterator(0);
    	for(bincount=0; bincount<randbin;  bincount++ )
    	{
    	    i.next();
    	}
    	
    	if (i.hasNext())
    	    chosen=(NMeasurable) i.next();
	if (chosen==null)	return;
        bincount=0;
    
        i = iScrapBin.getEntryList().listIterator(0);
        for(;i.hasNext();)
        {
            NMeasurable		c = (NMeasurable) i.next();
            
            if (c==chosen)	continue;
      	    double		d = c.distanceTo( chosen );
     	    if (d< iSizeOfNewBins)    bincount++;
        }
    
    	ListIterator		j;
        nn = null;
        j = iBins.listIterator(0);
        for(;j.hasNext();)
        {
            AutoClusterMemory	hb = (AutoClusterMemory) j.next();       
            double 		d = hb.getCentroid().distanceTo(chosen);
        
            if (hb.isConsolidated()==true)	continue;
            if (nn==null)
            {
                nn = hb;
                nn_dist = d;
            }else
            {
                if (d < nn_dist )
                {
                    nn=hb;
                    nn_dist=d;
                }
            }
        }
    
        if (nn==null)	return;
    
        //compare bin count to the number of entries in hb
        long	nncount = nn.getNumEntries();
        //count can be > size of scrap bin if the entry has consolidated
        //so if this is the case we need to set nncount to size of scrap bin else
        //we'll be unable to map the scrap bin data 
        if (nncount > iMaxNumInScrapBin)	nncount = iMaxNumInScrapBin;

        //
        //if we need a bigger bin just take the nn and increase its size
        //set the size of new bins parameter according to the size of the
        //neighbours?

        if ((double)bincount>0.75*(double)nncount)
        {
            if (iNumBins<iMaxNumBins)
      	    {
    	        //create a new bin , add in the points from the scrap bin
    	        //that are relevant
    	        if (iOutsideWorld.requestNewACM() ==true)
    	        {
    	            AutoClusterMemory	hb = new AutoClusterMemory
    	         			     (chosen,iSizeOfNewBins, iCurrentTime,iNextId++);
      	            iNumBins++;
       	            iBins.add(hb);
		    hb.storeDistance( 0.0, iCurrentTime );
       	            iOutsideWorld.setNewACM( hb );
    	    
  		    i = iScrapBin.getEntryList().listIterator(0);
       	            for(;i.hasNext();)
   	            {
   	                NMeasurable		c = (NMeasurable) i.next();
    		        double			d = c.distanceTo( chosen );
    	
	      	        if (d< iSizeOfNewBins )
	    	        {
	    	            addCT2Bin( c.createCopy(), hb );
	    	            i.remove();
	    	            //iScrapBin.getEntryList()->erase(i);
	    	        }
	            }
	        }
    	    }else
    	    {
    	        //increase the size of the nearest neighbour to include
    	        //the new bin
    	        if (nn!=null)
    	        {
     	            nn.setSize( nn_dist + iSizeOfNewBins );
     	            
     	            i = iScrapBin.getEntryList().listIterator(0);
      	            for(;i.hasNext();)
	            {
	                NMeasurable		c = (NMeasurable) i.next();
    		        double			d = c.distanceTo( nn.getCentroid() );
    	
	     	        if (d< nn.getSize())
	    	        {
	    	            addCT2Bin( c.createCopy(),nn );
	    	            //iScrapBin.getEntryList()->erase(i);
	    	            i.remove();
	    	        }
	            }    
    	        }
    	        else
    	        {
		    ;//I Need more bins
    	        }
    	    }
        }    
    }
    
    public	void	mergeBins( AutoClusterMemory primary, 
    				   AutoClusterMemory secondary)
    {
        if (iOutsideWorld.mergeACMs( primary , secondary )==false)
        	return;
    
        //remove the secondary and increase the size of the primary
        //(1) find the furtherst point in secondary from the primary centroid
        // 	  and set the new primary size accordingly
        ListIterator			i;
 	double				maxd=0,d;
    
        i = secondary.getEntryList().listIterator(0);
        for(; i.hasNext(); )
        {
            NMeasurable	c= (NMeasurable)  i.next();
        
            d = c.distanceTo(primary.getCentroid());
            if (maxd==0 || d>maxd)
            { maxd=d; }
        }
    
        primary.setSize( maxd );
        secondary.setIgnore(true);
        LinkedList			e;
        e = secondary.getEntryList();
	    
        //clamp the bin count
        int	m=iMaxNumBins;
        iMaxNumBins = iNumBins-1;  
        i = e.listIterator(0);
        for (; i.hasNext(); )
        {
            NMeasurable		c = (NMeasurable) i.next();
	    storeValue( c , true, iNumBins-1);//actung the ignored bin!
        }
        iMaxNumBins = m;    
    
        //now remove the bin
        ListIterator			j;
        j = iBins.listIterator(0);
        for(;j.hasNext();)
        {
            AutoClusterMemory	hb= (AutoClusterMemory) j.next();
        
            if (hb == secondary)
            {
            	if (iOutsideWorld.requestACMRemoval( hb ))
            	{  
        	    j.remove();//iBins.erase(j);
        	    iNumBins--;
        	    iOutsideWorld.removeACM( hb );
        	}
        	break;
       	    }
        }    
    }
    
    
    public	void		checkForBinSplits()
    {
        //if there are bins still available to use then check existing bins to 
        //see if they can be split into two bins
        //
        //Algo:
        //choose a random bin. if the size = size of new bins then just return
        //let's say for now that we can't go smaller than that
        //
        //chose a random point in the bin - this will probably be at a peak
        //count the number of points within size_of_new_bins. 
        //count the number of points outside that range
        //if the number inside is <10% or >85% then the bin is ok else
        //probably a split is needed
        if (iNumBins==0)	return;
        
    	AutoClusterMemory	chosen = null;
        int			i,j,n = (int)(iRand.nextDouble()*(double)iNumBins);
        ListIterator		hbit;
        ListIterator		cbit;

	hbit = iBins.listIterator(0);
	i=0;
        for(;hbit.hasNext();i++)
        {
            AutoClusterMemory	c = (AutoClusterMemory) hbit.next();
        
    	    if (i==n)	{chosen=c; break;}
        }
    
        if (chosen!=null)
        { if (chosen.isConsolidated())	return; }
    
        double	num_outside=0;
        double	num_inside=0;

        cbit = chosen.getEntryList().listIterator(0);
        for(; cbit.hasNext(); )
        {
            NMeasurable	c= (NMeasurable) cbit.next();
        
            if (c.distanceTo( chosen.getCentroid() ) < iSizeOfNewBins )
        	num_inside+=1.0;
            else
        	num_outside+=1.0;
        }
    
        if (num_inside< 0.1*num_outside || num_inside>0.85*num_outside)
            ; //ok
        else
        {
    	    chosen.incrNeedsToSplitCount();
            //if there is a bin available then split
            //need to request whether we can remove the bin before we proceed
            if (iOutsideWorld.requestACMRemoval( chosen ) )
            {
     	        if (iNumBins < iMaxNumBins)
    	        {
                    //remove the current bin, feed the points in again as normal
                    LinkedList		entries = chosen.getEntryList();
	            chosen.setIgnore(true);
	    
                    int			m=iMaxNumBins;
   	            iMaxNumBins = iNumBins-1;
	            cbit = entries.listIterator(0);
  	            for( ; cbit.hasNext();)
	            {
	                NMeasurable	c = (NMeasurable) cbit.next();
	                NMeasurable c2;
	                c2 = c.createCopy();
   	                storeValue( c2 , true, iNumBins-1);     
	            }
	            iMaxNumBins = m;
	    
	            //remove the existing entry
	            iOutsideWorld.removeACM( chosen );
	            hbit.remove();
 	    	    //bins.erase( hbit );
	            iNumBins--;
    	        }
    	    }
        }	
    }
    
    public	void		checkForNoiseBins()
    {
        if (iNumBins==0)	return;

	ListIterator		hbit, nexthbit;
	hbit= iBins.listIterator(0);
	for (;hbit.hasNext();)
	{
	    AutoClusterMemory	hb = (AutoClusterMemory) hbit.next();
    	
    	    if (hb.getNumEntries() == 1 && iCurrentTime-hb.getCreateTime() > iNoiseLifeTime )
    	    {
    	        if (iOutsideWorld.requestACMRemoval( hb ))
    	        {
    	            iOutsideWorld.removeACM( hb );
     	            hbit.remove();//bins.erase(hbit);
    	            iNumBins--;
    	        }
    	    }
        }
    }
    
	
    public	void    	checkForUnchangingBins()
    {
        //look for bins that have a lot of content and that are static
        //then remove the content and add a weight for future centroid calculations
        if (iNumBins==0)	return;
    
        AutoClusterMemory	chosen=null;
         int			i,j,n = (int)(iRand.nextDouble()*
         				(double) iNumBins);
    	ListIterator		hbit;
    	ListIterator		cit;
    	
    	hbit = iBins.listIterator(0);
        for(i=0;hbit.hasNext();i++)
        {
            AutoClusterMemory	acm = (AutoClusterMemory) hbit.next();
    	    if (i==n)	{chosen=acm; break;}
        }
    
        if (chosen!=null && chosen.isConsolidated()==false)
        {
	    //check to see how much the bin is changing
	    //how many points are going in and how much is it moving?
	    double	cc,ss;
	    cc = chosen.getCentroidChangeRatio();
	    ss = chosen.getSizeChangeRatio();
   	    if (cc < 1.0 && ss < 1.0 && chosen.getNeedsToSplitCount()<2)
	    {
	        chosen.consolidate();
	    
 	        //move chosen from the bin list to the consol_bin list.
	        iBins.remove(chosen);
	        iConsolBins.add(chosen);
	        iNumBins--;
 	    }
        }
    }
	
    public	void		addCT2Bin( NMeasurable c, AutoClusterMemory hb )
    {
        long	s = iMaxNumInScrapBin;
    
        if (hb==iScrapBin)	s*=10;
    	hb.addEntry( c );
	
	//(*1)
        if (hb.getEntryList().size() > s)
        {
            hb.removeFirstEntry();
        }
    }
}

